package com.algomypractice.linkedlist;

import com.sourcestruct.linearlist.SingleLinkedList;

/**
 * @author: ZhouBert
 * @date: 2019/6/7
 * @description: 删除链表的倒数第N个节点 给定一个链表，删除链表的倒数第 n 个节点并返回头结点。
 * 删除需要先找到【前驱节点】
 */
public class SingleLinkedDeleteNode {

	public static void main(String[] args) {
		SingleLinkedList lastnode = new SingleLinkedList(9, null);
		SingleLinkedList nodea = new SingleLinkedList(7, lastnode);
		SingleLinkedList nodeb = new SingleLinkedList(5, nodea);
		SingleLinkedList nodec = new SingleLinkedList(3, nodeb);
		SingleLinkedList noded = new SingleLinkedList(1, nodec);
		System.out.println(noded);

		deleteNodeByTwoPoint(noded,3);
		System.out.println(noded);
	}

	/**
	 * 最自然的想法，通过遍历一遍后回来N-1个节点，就是要删除的n个节点。但是要找出前驱节点，于是还需要遍历一遍，比较麻烦。
	 *
	 * @param node
	 * @param n
	 * @return
	 */
	public static SingleLinkedList deleteNodeByBack(SingleLinkedList node, int n) {
		int count = 0;
		return null;
	}

	/**
	 * 找到前驱节点
	 *
	 * @param node
	 * @param n
	 * @return
	 */
	public static SingleLinkedList deleteNodeByTwoPoint(SingleLinkedList node, int n) {
		SingleLinkedList curr = node;
		SingleLinkedList find = node;
		//找到前驱节点的指针
		int index = -1;
		//遍历单链表直到最后的节点
		while (curr != null) {
			curr=curr.getNext();
			index++;
			if (index>n){
				find=find.getNext();
			}
		}
		find.setNext(find.getNext().getNext());
		return node;
	}
}
